package com.wlj.utils.suanfa;

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Random;

/**
 * 给定一个字符串数组，数组中每个字符串都是一个01串，问用m个0和n个1最多可以组成数组中的多少个01串
 * 如:[10,0,1]，给定一个0和一个1，最多可以组成数组中的两个元素,0和1
 * F(i,m,n) 表示 用m个0和n个1最多可以组成[0...i]数组中的元素个数
 * F(i,m,n) =  F(i-1,m,n)    现有的m个0,n个1无法组成i元素，因此F(i,m,n)等于用m个0,n个1组成[0..i-1]数组最多元素的个数
 *             max(F(i-1,m,n) , F(i-1,m-m0(i), n-n0(i))   现有的m个0,n个1可以组成i元素,但是  还是分为考虑i和不考虑i，取最大值
 *                                                          m0(i)表示i元素含有的0的数量，n0(i)表示i元素含有的1的数量
 */
public class Suanfa07 {


    private static int[][][] aaa=null;
    public static int ones_zeroes(String[] strs, int m, int n){
        int size=strs.length;
        aaa=new int[size][m+1][n+1];
        for(int a=0;a<aaa.length;a++){
            for(int b=0;b<aaa[a].length;b++){
                for(int c=0;c<aaa[a][b].length;c++){
                    aaa[a][b][c]=-1;
                }
            }
        }
        return onezero(strs,size-1,m,n);
    }


    //用m个0,n个1可以最多组成[0..i]中多少个01串
    private static int onezero(String arr[],int i, int m, int n) {
        if (i<0){
            return 0;
        }
        if(m<=0&&n<=0){
            return 0;
        }
        if(aaa[i][m][n]>-1){
            return aaa[i][m][n];
        }
        int res=0;
        if(m>=nums(arr[i])[0]&&n>=nums(arr[i])[1]){
            res= Math.max(onezero(arr,i-1,m-nums(arr[i])[0],n-nums(arr[i])[1])+1,
                    onezero(arr,i-1,m,n));
        }else{
            res= onezero(arr,i-1,m,n);
        }
        aaa[i][m][n]=res;
        return res;
    }

    private static int[] nums(String s){
        int zn=0;
        int on=0;
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            if(aChar=='0'){
                zn++;
            }
            if(aChar=='1'){
                on++;
            }
        }
        int nums[]={zn,on};
        return nums;
    }

    public static String[] randoms(int n,int index){
        String[] strings = new String[n];
        for(int i=0;i<n;i++){
            int i1;
            int i2 = (int) (Math.random() * (index))+1;
            StringBuilder stringBuilder = new StringBuilder();
            for(int a=0;a<i2;a++){
                i1 = (int) (Math.random() * 2);
                stringBuilder.append(i1);
            }
            strings[i]=stringBuilder.toString();
        }
        return strings;
    }

    public static void main(String[] args) {
//        String arr[]=randoms(10, 3);
        String arr[]={"0","0","1","101001010"};
        long start = System.nanoTime(); //纳秒   1s=1*10^9 ns
        System.out.println(ones_zeroes(arr,3,2));
        long l = System.nanoTime() - start;
        System.out.println("耗时:"+new BigDecimal(l).divide(new BigDecimal(1000000000))+"s");
    }
}
